import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/10 14:54
 * @description 数位DP, 题目意思为 寻找 X<=N 且仅包含D中数字的X, 假设 N 有 K 位 ，那么 毫无疑问，当 x的位数小于 k时，X < N，k位数中，合法数有 D^k个
 */
public class Solution {
    public static void main(String[] args) {
        String[] digits = {"1", "3", "5", "7"};
        Solution solution = new Solution();
        solution.atMostNGivenDigitSet(digits, 56);
    }

    public int atMostNGivenDigitSet(String[] digits, int n) {
        // 首先将n转换为字符串，判断这个数有多少位
        String S = String.valueOf(n);
        int K = S.length();
        // 表示小于等于n中，最后|N| - i位数的合法数的个数， 例如 N=2345, dp[0]表示<=2345的合法数的个数，dp[1] 表示 <= 345的合法数的个数
        int[] dp = new int[K + 1];
        dp[K] = 1;

        // 计算当x为K位数的情况
        for (int i = K - 1; i >= 0; i--) {
            // 计算dp[i]
            int Si = S.charAt(i) - '0';
            for (String d : digits) {
                if (Integer.parseInt(d) < Si) {
                    // 如果当前位小于Si，那么后面K - i - 1位可以任意选取
                    dp[i] += Math.pow(digits.length, K - i - 1);
                } else if (Integer.parseInt(d) == Si) {
                    // 如果当前位等于Si, 那么要使合法，则满足条件的只能是低分位的合法数个数了。
                    dp[i] += dp[i + 1];
                }
            }
        }
        // 当x小于k位数，那么求等比数列的和
        for (int i = 1; i < K; i++) {
            dp[0] += Math.pow(digits.length, i);
        }
        return dp[0];
    }
}
